Dec 94 Challenge
Volume Number: 10
Issue Number: 12
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Mike Scanlin, Mountain View, CA
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
The rules
Here’s how it works: Each month we present a different programming challenge
here. First, you write some code that solves the challenge. Second, optimize your code
(a lot). Then, submit your solution to MacTech Magazine. We choose a winner based on
code correctness, speed, size and elegance (in that order of importance) as well as the
postmark of the answer. In the event of multiple equally-desirable solutions, we’ll
choose one winner at random (with honorable mention, but no prize, given to the
runners up). The prize for each month’s best solution is $50 and a limited-edition
“The Winner! MacTech Magazine Programming Challenge” T-shirt (not available in
stores).
To help us make fair comparisons, all solutions must be in ANSI compatible C
(e.g. don’t use Think’s Object extensions). Use only pure C code. We disqualify any
entries with any assembly in them (except for challenges specifically stated to be in
assembly). You may call any routine in the Macintosh toolbox (e.g., it doesn’t matter
if you use NewPtr instead of malloc). We test entries with the FPU and 68020 flags
turned off in THINK C. We time routines with the latest THINK C (with “ANSI
Settings”, “Honor ‘register’ first”, and “Use Global Optimizer” turned on), so
beware if you optimize for a different C compiler. Limit your code to 60 characters
wide. This helps with e-mail gateways and page layout.
We publish the solution and winners for this month’s Programmers’ Challenge
two months later. All submissions must be received by the 10th day of the month
printed on the front of this issue.
Mark solutions “Attn: Programmers’ Challenge Solution” and send them via
e-mail - Internet progchallenge@xplain.com, AppleLink MT.PROGCHAL, CompuServe
71552,174 and America Online MT PRGCHAL. Include the solution, all related files,
and your contact info. If you send via snail mail, send a disk with those items on it; see
“How to Contact Us” on p. 2.
MacTech Magazine reserves the right to publish any solution entered in the
Programming Challenge of the Month. Authors grant MacTech Magazine the
non-exclusive right to publish entries without limitation upon submission of each
entry. Authors retain copyrights for the code.
Rubik’s Cube
There are several things I’m good at. Solving Rubik’s Cube isn’t one of them. One
of my sadist friends gave me one last Christmas. I scramble it all the time and leave it
on my desk at work. Then I watch in amazement as any one of several co-workers
walks up to it and solves it within the amount of time it takes to ask “Mike, what’s the
fastest way to do buffered file I/O?” It’s very frustrating.
This month’s challenge idea comes not only from my own inadequacy but also
from Jim Lloyd (Mountain View, CA). The goal is to solve Rubik’s Cube.
The prototype of the function you write is:
/* 1 */
int
SolveRubiksCube(cubePtr)
RubiksCube *cubePtr;
Since I am so pathetic at solving the cube, I do not have enough insight to design
an effective data structure to represent it. You get to define the RubiksCube typedef
anyway you like.
Each call to SolveRubiksCube should make exactly one move. A move means
turning any side any direction by 90 degrees. The function returns one of 3 values on
each call to it:
/* 2 */
-1 illegal cube condition, can’t be solved
0 made a move, but not done yet
1 made the last move, it’s solved
Your routine will be called in a loop from my test bench something like this:
/* 3 */
ScrambleCube(cubePtr);
do {
x = SolveRubiksCube(cubePtr);
} while (x == 0);
Minimizing the number of moves to solve the cube is not important. Minimizing
the total time required to solve the cube is important. If your SolveRubiksCube routine
needs to keep track of some kind of state info or cached solution info between calls to it
then it may use static variables to do so (or, you could incorporate that info into the
RubiksCube data structure).
It is not required to detect an illegal cube condition on the first call to
SolveRubiksCube, just so long as it is detected eventually (i.e. don’t go into an infinite
loop if someone removes a couple of squares from your cube and puts them back in such
a way that it makes the cube unsolvable).
Because I will need to be able to watch your routine’s progress, you will need to
write two conversion routines:
/* 4 */
void
MikeCubeToRubiksCube(mikePtr, rubikPtr)
MikeCube *mikePtr;
RubiksCube *rubikPtr;
void
RubiksCubeToMikeCube(rubikPtr, mikePtr)
RubiksCube *rubikPtr;
MikeCube *mikePtr;
The purpose is to convert your cube from whatever data structure you come up
with into something my test bench can understand. It only knows about MikeCubes:
/* 5 */
typedef struct CubeSide {
char littleSquare[3][3];
} CubeSide;
typedef struct MikeCube {
CubeSide face[6];
} MikeCube;
A cube has 6 CubeSides. If you look at a cube straight on then the indexes are: 0 =
top, 1 = left side, 2 = front, 3 = right side, 4 = bottom, 5 = back. Within each
CubeSide there is a 3x3 array of littleSquares (first index is row, second index is
column). Each littleSquare is a number from 0 to 5, where each number represents
one of the 6 colors that make up a cube.
So, a solved cube would have all 9 of the littleSquares for each side set to the
same value. A solved cube that had the rightmost vertical column rotated
counterclockwise 90 degrees would look like this:
005
005
005
111220333
111220333
111220333
442
442
442
554
554
554
The top part (the 005 lines) represent the top of the cube after the rotation. The
220 pieces are what you see on the front, the 442 lines are what you see on the bottom
and the 554 pieces are what’s on the back. The value of mikePtr-> face[0].
littleSquare[1][2] is 5. The value of mikePtr->face[0].littleSquare[1][1] is 0 (the
center square of the top).
Write to me if you have questions on this. Your conversion routines are not going
to be part of your times so it doesn’t matter if they’re slow. Have fun.
Two Months Ago Winner
Based on the number of entries I received for the How Long Will It Take Challenge
I would have to say that software time estimates are even more difficult than their
well-deserved reputation implies. Either that or the typical Programmer Challenge
entrant isn’t concerned with schedules (or, at least, this Challenge). In any case,
congrats (and thanks) to Jeremy Vineyard (Lawrence, KS) for winning. I suppose the
fact that he was the only person to enter helped his entry somewhat but there are signs
of some careful thinking in his entry as well. (Although I must confess that I find the
inclusion of a Jolt Cola parameter completely useless. Mountain Dew on the other
hand...) This is Jeremy’s second 1st place showing (he also won the Insane Anglo
Warlord challenge in February, 1993). Nice job!
Jeremy’s entry refers to a book by E. Barne called “Estimation of Time-Space
Development Theorems” which I wasn’t, unfortunately, able to track down before my
column deadline. Sounds like something to check out, though, if you’re involved with
scheduling.
Here’s Jeremy’s winning solution:
Top 5 Excuses Why This Project Was Late:
1. “I though you said it was due NEXT month!”
2. The Product Manager quit after we missed the beta acceptance deadline.
3. Somebody activated the fire alarm while we were holding a brainstorming
session, and all our ideas were lost.
4. QA didn’t keep us up to date on active bugs.
5. I just couldn’t wait to try out the new game of solitaire that came with System
7.5!
The skill of the product manager is the key to a successful product.
/* 6 */
enum {
// Manager ratings.
noManager = 0,
lazyManager = 1,
poorManager = 2,
okManager = 3,
motivatedManager = 4,
excellentManager = 5
};
enum {
// System versions.
system7 = 7,
system6 = 6,
system5 = 5,
system4 = 4,
system3 = 3,
system2 = 2,
system1 = 1
};
// It assumed that the better the manager is, the more lines
// the engineers will be motivated to write.
#define juniorLines (100 + (20 * manager))
#define seniorLines (200 + (25 * manager))
// Every large project will have an overhead for planning,
// designing, and preparing for development.
#define overhead (linesC / 5000)
// These ratios are based on Barne’s matrix equations
// related to the study of time-space software development
// theorems. (trust me!)
#define PPCNativeRatio (float) (1.75 - (.02 * powerMacs))
#define joltRatio (float) (.7)
#define systemSupportRatio (float) (7.0 / systemSupport)
// Here again,the manager can motivate both QA and UI
// people to be more productive.
#define qaRatio 1 - (.1 + (.01 * manager) * qaPeople)
#define uiRatio (float) ((1.2 -
(.01 * manager)) * (seniorEng - uiPeople))
// Localization- a nightmare. Enough said.
#define localizedRatio (float) (1.35 * localized)
SoftwareTimeEstimate
A simplified algorithm that accurately calculates the time in calendar days for
any Macintosh software product to be completed.
The complete algorithm and collection of equations can be found in E. Barne’s
Estimation of Time-Space Development Theorems, published by Academic Press.
Implementation by Jeremy Vineyard, Lawrence, KS
/* 7 */
SoftwareTimeEstimate
unsigned short SoftwareTimeEstimate(linesC, seniorEng,
juniorEng, systemSupport, PPCNative, powerMacs, manager,
jolt, qaPeople, uiPeople, localized)
// Estimated # lines of source code in C.
unsigned long linesC;
// # of competent engineers with more than 5
// years experience.
unsigned short seniorEng;
// # of junior engineers with less than 2
// years experience.
unsigned short juniorEng;
// Earliest version of system software supported by
// product (1-7)
unsigned short systemSupport;
// TRUE if product will be PowerPC native.
Boolean PPCNative;
// # of PowerMacs available to developers (1-30).
unsigned short powerMacs;
// Rating of manager 1-5 (1 is poor, 5 is excellent)
// or 0 if none.
unsigned short manager;
// TRUE if company has steady supply of Jolt cola.
Boolean jolt;
// # of trained, in-house testers (most important).
unsigned short qaPeople;
// # of people responsible for making decisions about UI.
unsigned short uiPeople;
// # of Languages product must be localized to before
// shipping or 0 if none.
unsigned short localized;
{
float time, ratio;
short linesADay;
// Calculate the lines of source code that can be
// produced per day based upon the number of engineers
// working on the product.
// (Must have at least one engineer)
linesADay = (seniorEng * seniorLines)
+ (juniorEng * juniorLines);
// Estimate the # of days it will take to produce the
// specified amount of code.
time = (linesC / linesADay) + overhead;
// The farther backwards this product is compatible with
// system versions, the more time it will take to develop.
// systemSupport should be from 1 (System 1.0) to 7.
time *= systemSupportRatio;
// More development & QA time will need to be spent on
// a product that is PowerPC native. The more Power Macs
// that are available to developers, the faster the
// development & testing process will proceed.
if (PPCNative)
time *= PPCNativeRatio;
// o JOLT COLA! o
// o GIve the PRogramMeRS that EXtra ZING! to geT thEm o
// o MOTIVATED!! o
if (jolt)
time *= joltRatio;
// Quality assurance is one of the most important
// aspects of a product’s construction. Without it, the
// product will fail to reach the user base because of
// too many bugs. QA can never be overstaffed!
time *= qaRatio;
// User interface has a limited potential because people
// are likely to have very set opinions, and if there
// are too many UI people, it can kill a product. There
// should never be more UI personnel than engineers.
if (uiPeople > seniorEng)
time *= uiRatio;
// The more languages the product must be localized to
// before it can be shipped has a drastic effect on the
// development time.
if (localized)
time *= localizedRatio;
return (short) time;
}